#include "parafluidmultihashmap.h"

#include <vector>

using namespace ParaFluid;

AtomVoxelizer::Bucket::~Bucket()
{
	/* does nothing */
}

AtomVoxelizer::Bucket::Bucket()
	: _reservedSlotsOccupied(0)
	, _reservedSlots()
	, _extraSlots()
{
	/* does nothing */
}

AtomVoxelizer::Bucket::Bucket(const AtomVoxelizer::Bucket & other)
	: _reservedSlotsOccupied(other._reservedSlotsOccupied)
	, _reservedSlots()
	, _extraSlots(other._extraSlots)
{
	for(unsigned int i = 0; i < other._reservedSlotsOccupied; ++i)
	{
		_reservedSlots[i] = other._reservedSlots[i];
	}
}

AtomVoxelizer::Bucket & AtomVoxelizer::Bucket::operator= (const AtomVoxelizer::Bucket & rhs)
{
	if(&rhs != this)
	{
		_reservedSlotsOccupied = rhs._reservedSlotsOccupied;
	
		for(unsigned int i = 0; i < rhs._reservedSlotsOccupied; ++i)
		{
			_reservedSlots[i] = rhs._reservedSlots[i];
		}
	
		_extraSlots = rhs._extraSlots;
	}
	return *this;
}

void AtomVoxelizer::Bucket::serialize(QDataStream & stream) const
{
	stream << _reservedSlotsOccupied;
	for(unsigned int i = 0; i < MIN_SLOTS_PER_BUCKET; ++i)
	{
		stream << _reservedSlots[i];
	}
	
	stream << _extraSlots.size();
	for(unsigned int i = 0; i < _extraSlots.size(); ++i)
	{
		stream << _extraSlots[i];
	}
}

void AtomVoxelizer::Bucket::unserialize(QDataStream & stream)
{
	stream >> _reservedSlotsOccupied;
	for(unsigned int i = 0; i < MIN_SLOTS_PER_BUCKET; ++i)
	{
		stream >> _reservedSlots[i];
	}
	
	_extraSlots.clear();
	unsigned int count = 0;
	stream >> count;
	for(unsigned int i = 0; i < count; ++i)
	{
		Atom atom;
		stream >> atom;
		_extraSlots.push_back(atom);
	}
}

unsigned int AtomVoxelizer::Bucket::occupiedSlots() const
{
	return _reservedSlotsOccupied + _extraSlots.size();
}

void AtomVoxelizer::Bucket::append(const Atom & atom)
{
	if(_reservedSlotsOccupied < MIN_SLOTS_PER_BUCKET)
	{
		_reservedSlots[_reservedSlotsOccupied] = atom;
	
		++_reservedSlotsOccupied;
	}
	else
	{
		_extraSlots.push_back(atom);
	}
}

void AtomVoxelizer::Bucket::remove(const Atom & atom)
{
	bool notFound = true;
	for(int i = _reservedSlotsOccupied; i >= 0 && notFound; --i)
	{
		if(_reservedSlots[i] == atom)
		{
			removeReserved(i);
			notFound = false;
		}
	}
	for(int i = _extraSlots.size(); i >= 0 && notFound; --i)
	{
		if(_extraSlots[i] == atom)
		{
			removeExtra(i);
			notFound = false;
		}
	}
}

void AtomVoxelizer::Bucket::removeReserved(unsigned int slot)
{
	if(slot < MIN_SLOTS_PER_BUCKET)
	{
		// If Removed Slot is not the Last Occupied Reserved Slot
		if(slot < _reservedSlotsOccupied - 1)
		{
			// Assign Removed Slot with Last Occupied Reserved Slot
			_reservedSlots[slot] = _reservedSlots[_reservedSlotsOccupied - 1];
		}
		
		// If Extra Slots are Empty
		if(_extraSlots.empty())
		{
			// Decrease the number of Occupied Reserved Slots
			--_reservedSlotsOccupied;
		}
		else
		{
			// Assign Last Reserved Slot to the First Extra Slot
			_reservedSlots[MIN_SLOTS_PER_BUCKET - 1] = _extraSlots.at(0);
			
			// Remove First Extra Slot
			_extraSlots.erase(_extraSlots.begin());
		}
	}
}

void AtomVoxelizer::Bucket::removeExtra(unsigned int slot)
{
	if(slot < _extraSlots.size())
	{
		_extraSlots.erase(_extraSlots.begin() += slot);
	}
}

void AtomVoxelizer::Bucket::clear()
{
	// Reset the number of Occupied Reserved Slots to Zero
	_reservedSlotsOccupied = 0;

	// Clear Extra Slots
	_extraSlots.clear();
}

void AtomVoxelizer::Bucket::acceptVisitor(AtomVoxelizer::ReadWriteVisitor & visitor)
{
	for(unsigned int i = 0; i < _reservedSlotsOccupied; ++i)
	{
		visitor.visit(_reservedSlots[i]);
	}
	for(unsigned int i = 0; i < _extraSlots.size(); ++i)
	{
		visitor.visit(_extraSlots[i]);
	}
}

void AtomVoxelizer::Bucket::acceptVisitor(AtomVoxelizer::ReadOnlyVisitor & visitor) const
{
	for(unsigned int i = 0; i < _reservedSlotsOccupied; ++i)
	{
		visitor.visit(_reservedSlots[i]);
	}
	for(unsigned int i = 0; i < _extraSlots.size(); ++i)
	{
		visitor.visit(_extraSlots[i]);
	}
}

void AtomVoxelizer::Bucket::acceptVisitor(ReadWriteVisitor & visitor, int indexFirst, int indexLast)
{
	int first = indexFirst;
	int last = indexLast;
	
	for(unsigned int i = 0; i < _reservedSlotsOccupied && first <= last; ++i)
	{
		visitor.visit(_reservedSlots[i]);
		first++;
	}
	for(unsigned int i = 0; i < _extraSlots.size() && first <= last; ++i)
	{
		visitor.visit(_extraSlots[i]);
		first++;
	}
}

AtomVoxelizer::~AtomVoxelizer()
{
	/* does nothing */
}

AtomVoxelizer::AtomVoxelizer()
	: _smoothingDistance(1.0)
	, _buckets(100)
{
	/* does nothing */
}

AtomVoxelizer::AtomVoxelizer(unsigned int buckets, float smoothingDistance)
	: _smoothingDistance(smoothingDistance)
	, _buckets(buckets)
{
	/* does nothing */
}

AtomVoxelizer::AtomVoxelizer(const AtomVoxelizer & other)
	: _smoothingDistance(1.0)
	, _buckets(other._buckets)
{
	/* does nothing */
}

AtomVoxelizer & AtomVoxelizer::operator= (const AtomVoxelizer & rhs)
{
	if(&rhs != this)
	{
		_buckets = rhs._buckets;
	}
	return *this;
}

void AtomVoxelizer::serialize(QDataStream & stream) const
{
	stream << _smoothingDistance;
	stream << _buckets.size();
	for(unsigned int i = 0; i < _buckets.size(); ++i)
	{
		_buckets[i].serialize(stream);
	}
}

void AtomVoxelizer::unserialize(QDataStream & stream)
{
	unsigned int count = 0;
	stream >> _smoothingDistance;
	stream >> count;
	_buckets.clear();
	for(unsigned int i = 0; i < count; ++i)
	{
		Bucket bucket;
		bucket.unserialize(stream);
		_buckets.push_back(bucket);
	}
}

const float & AtomVoxelizer::smoothingDistance() const
{
	return _smoothingDistance;
}

void AtomVoxelizer::setSmoothingDistance(const float & value)
{
	_smoothingDistance = value;
}

void AtomVoxelizer::insert(const Atom & atom)
{
	_buckets[hash(voxelize(atom.currentPosition)) % _buckets.size()].append(atom);
}

void AtomVoxelizer::remove(const Atom & atom)
{
	_buckets[hash(voxelize(atom.currentPosition)) % _buckets.size()].remove(atom);
}

void AtomVoxelizer::clear()
{
	for(unsigned int i = 0; i < _buckets.size(); ++i)
	{
		_buckets[i].clear();
	}
}

void AtomVoxelizer::rehash()
{
	
	class Saver
		: public AtomVoxelizer::ReadOnlyVisitor
	{
		
	public:
		
		std::vector<Atom> result;
		
		Saver()
			: result()
		{
			/* does nothing */
		}
		
		void visit(const Atom & atom)
		{
			result.push_back(atom);
		}
		
	} visitor;
	
	acceptVisitor(visitor);
	
	clear();
	
	for(std::vector<Atom>::iterator i = visitor.result.begin(); i != visitor.result.end(); ++i)
	{
		insert(*i);
	}
	
}

void AtomVoxelizer::acceptVisitor(ReadWriteVisitor & visitor)
{
	for(unsigned int i = 0; i < _buckets.size(); ++i)
	{
		_buckets[i].acceptVisitor(visitor);
	}
}

void AtomVoxelizer::acceptVisitor(ReadOnlyVisitor & visitor) const
{
	for(unsigned int i = 0; i < _buckets.size(); ++i)
	{
		_buckets[i].acceptVisitor(visitor);
	}
}

void AtomVoxelizer::acceptVisitor(ReadWriteVisitor & visitor, const Vector & position)
{
	_buckets[hash(voxelize(position)) % _buckets.size()].acceptVisitor(visitor);
}

void AtomVoxelizer::acceptVisitor(ReadOnlyVisitor & visitor, const Vector & position) const
{
	_buckets[hash(voxelize(position)) % _buckets.size()].acceptVisitor(visitor);
}

void AtomVoxelizer::acceptVisitor(ReadWriteVisitor & visitor, int indexFirst, int indexLast)
{
	int currentBucketBegin = 0;
	int currentBucketEnd = 0;
	
	int first = 0;
	int last = 0;
	
	for(unsigned int i = 0; i < _buckets.size(); ++i)
	{
		currentBucketEnd = currentBucketBegin + _buckets[i].occupiedSlots();
		
		if(currentBucketBegin <= indexFirst && indexFirst <= currentBucketEnd || currentBucketBegin <= indexLast && indexLast <= currentBucketEnd)
		{
			if(indexFirst < currentBucketBegin)
			{
				first = currentBucketBegin;
			}
			else
			{
				first = indexFirst;
			}
			if(indexLast > currentBucketEnd)
			{
				last = currentBucketEnd;
			}
			else
			{
				last = indexLast;
			}
			
			_buckets[i].acceptVisitor(visitor, first, last);
		}
		
		currentBucketBegin += _buckets[i].occupiedSlots();
	}
	
}

Vector AtomVoxelizer::voxelize(const Vector & position) const
{
	Vector result(position);
	
	result.x = int(result.x / _smoothingDistance) * _smoothingDistance;
	result.y = int(result.y / _smoothingDistance) * _smoothingDistance;
	result.z = int(result.z / _smoothingDistance) * _smoothingDistance;
	
	return result;
}

unsigned int AtomVoxelizer::hash(const Vector & voxel) const
{
	register const unsigned int prime0 = 73856093;
	register const unsigned int prime1 = 19349663;
	register const unsigned int prime2 = 83492791;
	unsigned int ux = voxel.x;
	unsigned int uy = voxel.y;
	unsigned int uz = voxel.z;
	return (ux * prime0) ^ (uy * prime1) ^ (uz * prime2);
}

QDataStream & operator<< (QDataStream & stream, const ParaFluid::AtomVoxelizer & atomVoxelizer)
{
	atomVoxelizer.serialize(stream);
	return stream;
}

QDataStream & operator>> (QDataStream & stream, ParaFluid::AtomVoxelizer & atomVoxelizer)
{
	atomVoxelizer.unserialize(stream);
	return stream;
}
